/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-25
 * Time: 17:11
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode tail1 = head;
        ListNode head2 = head.next;
        ListNode tail2 = head2;
        ListNode cur = tail2.next;
        // 1 代表 奇数, -1 代表 偶数
        int flag = 1;
        while (cur != null) {
            if (flag == 1) {
                // 奇数
                tail1.next = cur;
                tail1 = tail1.next;
            }else {
                // 偶数
                tail2.next = cur;
                tail2 = tail2.next;
            }
            cur = cur.next;
            flag = - flag;
        }
        // 最后将偶数链表的结尾置空, 否则出现环
        tail2.next = null;
        // 将两个链表连接起来
        tail1.next = head2;
        return head;
    }
}
